/**
 * @version: V1.0
 * @Title: CustomHeap.java
 * @Description:
 * @author wangshipeng
 * @date 2022-01-12 22:15
 * @Copyright: 2022-01-12
 */

package com.peng.heap;

/**
 * @author wangshipeng
 * @ClassName: CustomHeap
 * @Description:
 * @date 2022-01-12 22:15
 */
public class MyBaseHeap {
    private int[] originArr;
    private int heapSize;
    private int limit;

    public MyBaseHeap(int limit) {
        //0位置弃而不用，从1位置开始表示数据
        this.originArr = new int[limit + 1];
        this.limit = limit;
        this.heapSize = 0;
    }

    public static void main(String[] args) {

        MyBaseHeap heap = new MyBaseHeap(10);
        heap.push(3);
        heap.push(5);
        heap.push(6);
        heap.push(7);
        heap.push(8);
        heap.push(9);
        System.out.println(heap.pop());
        System.out.println(heap.pop());
        System.out.println(heap.pop());
        System.out.println(heap.pop());
        System.out.println(heap.pop());
        System.out.println(heap.pop());
        System.out.println(heap.pop());
    }

    public void push(int val) {
        if (limit == heapSize) {
            throw new RuntimeException("堆已经满啦。。。");
        }
        originArr[++heapSize] = val;
        heapInsert(heapSize);
    }

    public int pop(){
        if(heapSize==0){
            throw new RuntimeException("堆已经空啦。。。");
        }
        int top = originArr[1];
        swap(1,heapSize--);
        heapify(1);
        return top;
    }

    private void heapInsert(int index) {
        while (index >> 1 != 0 && originArr[index] > originArr[index >> 1]) {
            swap(index, index >> 1);
            index >>= 1;
        }
    }

    private void heapify(int index) {
        int left = index << 1;
        while (left< heapSize) {
            int right = left | 1;
            int pos = right > heapSize ? left : (originArr[right] > originArr[left] ? right : left);
            int choosePos = originArr[index] < originArr[pos] ? pos : index;
            if(choosePos==index){
                break;
            }
            swap(index,choosePos);
            left <<= 1;
        }


    }

    private void swap(int i, int j) {
        int temp = originArr[i];
        originArr[i] = originArr[j];
        originArr[j] = temp;
    }


}
